'''
@author:Kevin Zhao
@date:Jan 8,2013
@note: 
binary tree(unsorted,self-balanced)
tree with unbounded branching(arbitrary number of children of a tree node)
'''
from queue import SinglyLinkedQueue

'''
binary tree(unsorted,self-balanced)
'''
class binary_tree_node:
    value = None
    parent = None
    left = None
    right = None
    children_size = 0
    
class binary_tree:
    root = None
    temp_queue = SinglyLinkedQueue()
    def __init__(self, value):
        self.root = self.newNode(value)
    def newNode(self,value):
        node = binary_tree_node()
        node.value = value
        return node
    def __getNode(self,root,value):
        if root == None:
            return None
        if value == root.value:
            return root
        node = self.__getNode(root.left, value)
        if node == None:
            node = self.__getNode(root.right, value)
        return node
    def getNode(self,value):
        if value =="ROOT":
            return self.root
        else:
            return self.__getNode(self.root, value)
    '''
    O(lgN) time complexity insertion method
    '''
    def __insert(self,root,value):
        while True:
            #root is full,meaning it has a children size equal to 2
            if root.children_size ==2:
                #doing BFS
                self.temp_queue.enqueue(root.left)
                self.temp_queue.enqueue(root.right)
                root = self.temp_queue.dequeue()
                continue
            #root is not full
            else:
                self.temp_queue.clear()
                if root.left == None:
                    node = self.newNode(value)
                    root.left = node
                    node.parent = root
                    root.children_size +=1
                    return
                if root.right == None:
                    node = self.newNode(value)
                    root.right = node
                    node.parent = root
                    root.children_size +=1
                    return
                
            
            
    def random_insert(self,value):
        if self.root == None:
            self.root = self.newNode(value)
        else:
            self.__insert(self.root, value)
    def insertAsLeftChild(self,parent_value,value):
        parent_node = self.getNode(parent_value)
        node = self.newNode(value)
        node.parent = parent_node
        parent_node.left = node
    def insertAsRightChild(self,parent_value,value):
        parent_node = self.getNode(parent_value)
        node = self.newNode(value)
        node.parent = parent_node
        parent_node.right = node
'''
Unbounded branching Tree
'''
class ubb_tree_node:
    value = None
    parent = None
    left = None
    right_sibling = None
    
class ubb_tree:
    root = None
    '''
    value:root node value
    '''
    def __init__(self, value):
        self.root = self.newNode(value)
    def newNode(self,value):
        node = ubb_tree_node()
        node.value = value
        return node
    def __getNode(self,root,value):
        if root == None:
            return None
        if value == root.value:
            return root
        node = self.__getNode(root.right_sibling, value)
        if node == None:
            node = self.__getNode(root.left, value)
        return node
    def getNode(self,value):
        if value =="ROOT":
            return self.root
        else:
            return self.__getNode(self.root, value)
    def insertAsChild(self,parent_value,value):
        parent_node = self.getNode(parent_value)
        if parent_node.left == None:
            node = self.newNode(value)
            node.parent = parent_node
            parent_node.left = node
        else:
            while True:
                right_sibling_node = parent_node.right_sibling
                if right_sibling_node == None:
                    break
                else:
                    parent_node = right_sibling_node
            node = self.newNode(value)
            node.parent = parent_node
            parent_node.right_sibling = node
                
